AVL Tree
Q1.
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a,b]? Assume that the number of reported elements is k.Q2.
What is the worst case time complexity of inserting n^2 elements into an AVL-tree with n elements initially?Q5.
Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^{a}log^{b}n+m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is _______.Q6.
The number of rotations required to insert a sequence of elements 9, 6, 5, 8, 7, 10 into an empty AVL tree is?Q7.
The worst case running time to search for an element in a balanced binary search tree with n2^{n} elements isQ8.
What is the maximum height of any AVL-tree with 7 nodes? Assume that the height of a tree with a single node is 0.Q9.
A program takes as input a balanced binary search tree with n leaf nodes and computes the value of a function g(x) for each node x. If the cost of computing g(x) is min{no. of leaf-nodes in left-subtree of x, no. of leaf-nodes in right-subtree of x} then the worst-case time complexity of the program isQ10.
In the balanced binary tree in the below figure, how many nodes will become unbalanced when a node is inserted as a child of the node g?